package Lee_code;

import java.util.Arrays;

public class Lee_322_dp_2 {
    public int coinChange(int[] coins, int amount) {
        Arrays.sort(coins);
        int len = coins.length;
        int[] dp = new int[amount+1];

        Arrays.fill(dp, len);
        dp[0] = 0;

        // 先物品后背包 dp[i]代表最少的硬币个数
        for (int i=0; i<len; i++){
            for (int j=1; j<=amount;j++){
                dp[j] = Math.min(dp[j], dp[j-coins[i]]+1);
            }
        }

        return dp[amount]==len?-1:dp[amount];
    }
}
